class Solution:
    _MOD = 10 ** 9 + 7

    def numWays(self, steps: int, arrLen: int) -> int:
        size = min(501, arrLen)

        dp1 = [0] * size
        dp1[0] = 1

        for _ in range(steps):
            dp2 = [0] * size
            for i in range(size):
                dp2[i] = (dp1[i - 1] if i > 0 else 0) + dp1[i] + (dp1[i + 1] if i + 1 < size else 0)
            dp1 = dp2

        return dp1[0] % self._MOD


if __name__ == "__main__":
    print(Solution().numWays(3, 2))  # 4
    print(Solution().numWays(2, 4))  # 2
    print(Solution().numWays(4, 2))  # 8
